package Dynamic_programming;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

/**
 * @Description: $
 * @Param: $
 * @return: $
 * @Author 万家欣
 * @Date: 2022/6/2
 * Algorithm
 * @Version 1.0
 */
public class tea {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root ==null){
            return root;
        }
        if(root.val < key){
            root.right = deleteNode(root.right,key);
        }else if(root.val > key){
            root.left = deleteNode(root.left,key);
        }else {
            if ( root.left == null)   return root.right; // 情况1，欲删除节点无左子
            if ( root.right == null)  return root.left;  // 情况2，欲删除节点无右子
            TreeNode  node = root.right;           // 情况3，欲删除节点左右子都有
            while (node.left != null) {          // 寻找欲删除节点右子树的最左节点
                node = node.left;
                node.left = root.left;    // 将欲删除节点的左子树成为其右子树的最左节点的左子树
                root = root.right;         // 欲删除节点的右子顶替其位置，节点被删除
            }
        }
        return root;
    }
    public int fib(int n) {
        int e = 1000000007;
    int a = 0,b = 1;
    if(n < 2){
        return n;
    }
        for (int i = 3; i <= n ; i++) {
            int c = a+b;
            a = b;
            b = c%e;
        }
        return b%e;
    }


    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 次数，行数
        int times = scanner.nextInt();
        List<String> list = new ArrayList<>();
        for (int i = 0; i < times; i++) {
            // 每一行
            list.add(scanner.next());
        }
    }
    public TreeNode addOneRow(TreeNode root, int v, int d) {
        if(d == 0 || d == 1){//递归结束条件
            TreeNode t = new TreeNode(v);
            if(d == 1){
                t.left = root;
            }else {
                t.right = root;
            }
            return t;
        }
        if(root != null&& d > 1){
            root.left  = addOneRow(root.left,v,d > 2 ? d - 1 : 1);
            root.right = addOneRow(root.right,v,d > 2 ? d - 1 : 0);
        }
        return root;
    }

    public int search(int[] nums, int target) {
    int l = 0;
    int r = nums.length - 1;
    while (l <= r){
        int mid = l  +(r - l) / 2;
        if(nums[mid] < target){
            l = mid;
        }else if(nums[mid] >target){
            r = mid - 1;
        }else {
            return mid;
        }
    }
    return  -1;
    }
    public int[] runningSum(int[] nums) {
    int[] sum = new int[nums.length];
    sum[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            sum[i] = nums[i] +sum[i -1];
        }
        return sum;
    }
    @Test
    public  void  dd(){
        String s = "COL16 COL17 COL18 COL19 COL20 COL21 COL22 COL23 COL24 COL25 COL26 COL27 COL28 COL29 COL30 COL31 COL32 COL33 COL34 COL35 COL36 COL37 COL38 COL39 COL40 COL41 COL42 COL43 COL44 COL45 COL46 COL47 COL48 COL49 COL50 COL51 COL52 COL53 COL54 COL55 COL56 COL57 COL58 COL60 COL61 COL63 COL64 COL65 COL66 COL67 COL68 COL69 COL70 COL71 COL72 COL336 COL337 COL73 COL75 COL76 COL77 COL80 COL81 COL82 COL84 COL86 COL87 COL89 COL90 COL91 COL92 COL93 COL95 COL96 COL97 COL99 COL101 COL102 COL341 COL109 COL110 COL111 COL112 COL113 COL114 COL115 COL116 COL117 COL118 COL119 COL120 COL123 COL124 COL125 COL126 COL127 COL128 COL129 COL133 COL340 COL356";
        String[] sss = s.split(" ");
        System.out.printf(String.valueOf(sss.length));
        pivotIndex(new int[]{1, 7, 3, 6, 5, 6});
    }
    public int pivotIndex(int[] nums) {
        int sum = 0;
        for (int x:nums) {
            sum += x;
        }

        int index = 0;
        for (int i = 0; i < nums.length; i++) {
          int x = nums[i];
            index = index + x;
            if(index  == sum - index) {
                return i;
            }
        }
        return -1;
    }
    public int singleNumber(int[] nums) {
        int n = nums[0];
        for (int i = 1; i < nums.length; i++) {
            n ^= nums[i];
        }
        return n;
    }

    public int majorityElement(int[] nums) {
    int count = 1;
    int n = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if(n == nums[i]){
                count++;
            }else {
                count --;
                if(count == 0){
                    n = nums[i];
                    count = 1;
                }
            }
        }
        return n;
    }

    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> lists = new ArrayList<>();
        Arrays.sort(nums);
        if(nums[0] > 0){
            return lists;
        }

        for (int i = 0; i < nums.length - 2; i++) { // O(n^2)
            if (nums[i] > 0) break; // 第一个数大于 0，后面的数都比它大，肯定不成立了
            if (i > 0 && nums[i] == nums[i - 1]) continue; // 去掉重复情况
            int target = -nums[i];
            int left = i + 1, right = nums.length - 1;
            while (left < right) {
                if (nums[left] + nums[right] == target) {
                    lists.add(new ArrayList<>(Arrays.asList(nums[i], nums[left], nums[right])));

                    // 现在要增加 left，减小 right，但是不能重复，比如: [-2, -1, -1, -1, 3, 3, 3], i = 0, left = 1, right = 6, [-2, -1, 3] 的答案加入后，需要排除重复的 -1 和 3
                    left++; right--; // 首先无论如何先要进行加减操作
                    while (left < right && nums[left] == nums[left - 1]) left++;
                    while (left < right && nums[right] == nums[right + 1]) right--;
                } else if (nums[left] + nums[right] < target) {
                    left++;
                } else {  // nums[left] + nums[right] > target
                    right--;
                }
            }
        }
        return lists;
    }
}

